package collection

import (
	"fmt"
	"strings"
	"sync"
)

// TreeNodeSync 树形数据结构, 单向链机制设计(有锁, 并发安全)
type TreeNodeSync[D TreeID, V any] struct {
	id       D                     //节点ID (不能为零值)
	pid      D                     //父级节点ID (Root节点其PID通常为零值)
	value    V                     //节点值Any (Root节点为Value零值)
	parent   *TreeNodeSync[D, V]   //父级节点
	children []*TreeNodeSync[D, V] //下级节点列表
	size     int                   //下级节点长度
	mu       *sync.RWMutex
}

// NewTreeSync 建立一个新的树形数据结构, 单向链机制设计(有锁, 并发安全)
func NewTreeSync[D TreeID, V any]() *TreeNodeSync[D, V] {
	root := new(TreeNodeSync[D, V])
	root.parent = nil
	root.children = []*TreeNodeSync[D, V]{}
	root.mu = new(sync.RWMutex) // 根节点创建读写锁, 其他节点的锁统一使用(执行)更节点的锁
	return root
}

// IsRoot 是否是根节点
func (n *TreeNodeSync[D, V]) IsRoot() bool {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n.parent == nil
}

// IsLeaf 是否是叶子节点(末节点,没有下级节点)
func (n *TreeNodeSync[D, V]) IsLeaf() bool {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n.size == 0
}

// Size 获取下级节点长度
func (n *TreeNodeSync[D, V]) Size() int {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n.size
}

// ID 获取单前节点的ID
func (n *TreeNodeSync[D, V]) ID() D {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n.id
}

// PID 获取单前节点的父级PID
func (n *TreeNodeSync[D, V]) PID() D {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n.pid
}

// Value 获取单前节点的值
func (n *TreeNodeSync[D, V]) Value() V {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n.value
}

// Parent 获取单前节点的父节点
func (n *TreeNodeSync[D, V]) Parent() *TreeNodeSync[D, V] {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n.parent
}

// Children 获取下级节点列表
func (n *TreeNodeSync[D, V]) Children() []*TreeNodeSync[D, V] {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n.children
}

// Root 获取ROOT根节点
func (n *TreeNodeSync[D, V]) Root() (root *TreeNodeSync[D, V]) {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n._root()
}

// _root 获取ROOT根节点(无锁方法)
func (n *TreeNodeSync[D, V]) _root() (root *TreeNodeSync[D, V]) {
	if n.parent == nil {
		return n
	}
	root = n
	for root.parent != nil {
		root = root.parent
	}
	return
}

// isValidID 检查ID是否有效 (ID要大于零值)
func (n *TreeNodeSync[D, V]) isValidID(v D) bool {
	var zero D
	return v > zero
}

// SeacrhBFS 广度优先搜素 (范围: 当前节点及下级树形节点)
func (n *TreeNodeSync[D, V]) SeacrhBFS(ID D) (node *TreeNodeSync[D, V], ok bool) {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n._seacrhBFS(ID)
}
func (n *TreeNodeSync[D, V]) _seacrhBFS(ID D) (node *TreeNodeSync[D, V], ok bool) {
	if n.id == ID {
		return n, true
	}
	if n.size == 0 || !n.isValidID(ID) {
		return nil, false
	}
	//先进先出, 搜索队列
	queue := NewQueue[*TreeNodeSync[D, V]]()
	queue.Push(n.children...)
	for !queue.IsEmpty() {
		//消费队列节点
		val, ok := queue.Pop()
		if !ok {
			return nil, false
		}
		//检查它是否匹配，如果该节点未匹配，则继续下一个节点
		if val.id == ID {
			return val, true
		}
		//当前节点如有子节点，把所有子节点都加入队列
		if val.size > 0 {
			queue.Push(val.children...)
		}
	}
	return nil, false
}

// SeacrhFullBFS 广度优先搜素 (范围: 全树搜索)
func (n *TreeNodeSync[D, V]) SeacrhFullBFS(ID D) (node *TreeNodeSync[D, V], ok bool) {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n._root()._seacrhBFS(ID)
}

// SeacrhDFS 深度优先搜素 (范围: 当前节点及下级树形节点)
func (n *TreeNodeSync[D, V]) SeacrhDFS(ID D) (node *TreeNodeSync[D, V], ok bool) {
	n.mu.RLock()
	defer n.mu.RUnlock()
	return n._seacrhDFS(ID)
}
func (n *TreeNodeSync[D, V]) _seacrhDFS(ID D) (node *TreeNodeSync[D, V], ok bool) {
	if n.id == ID {
		return n, true
	}
	if n.size == 0 || !n.isValidID(ID) {
		return nil, false
	}
	//先进后出, 搜索栈
	stack := NewStack[*TreeNodeSync[D, V]]()
	stack.Push(n.children...)
	for !stack.IsEmpty() {
		//消费出栈
		val, ok := stack.Pop()
		if !ok {
			return nil, false
		}
		//检查它是否匹配，如果该节点未匹配，则继续下一个节点
		if val.id == ID {
			return val, true
		}
		//当前节点如有子节点，把所有子节点都加入栈
		if val.size > 0 {
			stack.Push(val.children...)
		}
	}
	return nil, false
}

// SeacrhFullDFS 深度优先搜素 (范围: 全树搜索)
func (n *TreeNodeSync[D, V]) SeacrhFullDFS(ID D) (node *TreeNodeSync[D, V], ok bool) {
	return n._root()._seacrhDFS(ID)
}

func (n *TreeNodeSync[D, V]) _makeNode(ID, PID D, Value V) *TreeNodeSync[D, V] {
	newNode := new(TreeNodeSync[D, V])
	newNode.parent = n
	newNode.id = ID
	newNode.pid = PID
	newNode.value = Value
	newNode.mu = n.mu
	return newNode
}

// Push 添加一个子节点到当前节点的Children, 返回新节点 TreeNodeSync
//   - ID: 节点ID
//   - Value: 节点值Any
//   - 插入失败或ID无效/重复时, 返回错误信息
func (n *TreeNodeSync[D, V]) Push(ID D, Value V) (newNode *TreeNodeSync[D, V], err error) {
	n.mu.Lock()
	defer n.mu.Unlock()
	// ID 无效
	if !n.isValidID(ID) {
		return nil, fmt.Errorf("ID Invalid")
	}
	// ID 异常
	if n.id == ID || n.pid == ID {
		return nil, fmt.Errorf("ID Invalid")
	}
	// ID 重复(环路)
	if _, ok := n._root()._seacrhBFS(ID); ok {
		return nil, fmt.Errorf("ID Repeat")
	}
	if n.children == nil {
		n.children = []*TreeNodeSync[D, V]{}
	}
	newNode = n._makeNode(ID, n.id, Value)
	n.children = append(n.children, newNode)
	n.size++
	return newNode, nil
}

// Delete 删除当前节点下的某一个Children子节点
func (n *TreeNodeSync[D, V]) Delete(ID D) bool {
	n.mu.Lock()
	defer n.mu.Unlock()
	// ID 无效
	if !n.isValidID(ID) {
		return false
	}
	if n.children == nil {
		return false
	}
	for i, v := range n.children {
		if v.id == ID {
			v = nil
			n.children = append(n.children[:i], n.children[i+1:]...)
			n.size--
			return true
		}
	}
	return false
}

// Remove 删除当前节点(删除自己)
func (n *TreeNodeSync[D, V]) Remove() bool {
	n.mu.Lock()
	defer n.mu.Unlock()
	if n.parent == nil {
		// 根节点不能删除
		return false
	}
	if n.parent.children == nil {
		// 该节点已不存在
		return false
	}
	for i, v := range n.parent.children {
		if v.id == n.id {
			n.parent.children = append(n.parent.children[:i], n.parent.children[i+1:]...)
			n.parent.size--
			n = nil
			return true
		}
	}
	return false
}

// Clear 清空当前节点所有Children子节点
func (n *TreeNodeSync[D, V]) Clear() bool {
	n.mu.Lock()
	defer n.mu.Unlock()
	if n.children == nil {
		return false
	}
	n.children = nil
	n.size = 0
	return true
}

// ToSliceMapTree 生成多维结构的目录树
//   - fn: 函数自定义Map节点，返回map[string]any
//   - childItemName: 子节点名称，如："sub"
func (n *TreeNodeSync[D, V]) ToSliceMapTree(fn func(node *TreeNodeSync[D, V]) map[string]any, childItemName string) (lines []map[string]any) {
	n.mu.RLock()
	defer n.mu.RUnlock()
	if n.size == 0 {
		return []map[string]any{}
	}
	return n._toSliceMapTree(fn, childItemName, n.children)
}
func (n *TreeNodeSync[D, V]) _toSliceMapTree(fn func(node *TreeNodeSync[D, V]) map[string]any, childItemName string, children []*TreeNodeSync[D, V]) []map[string]any {
	if children == nil {
		return []map[string]any{}
	}
	maps := make([]map[string]any, 0, len(children))
	for _, v := range children {
		nMap := fn(v)
		if v.size > 0 {
			nMap[childItemName] = v._toSliceMapTree(fn, childItemName, v.children)
		} else {
			nMap[childItemName] = []map[string]any{}
		}
		maps = append(maps, nMap)
	}
	return maps
}

// ToSliceMapList 生成一维结构的目录树
//   - fn: 函数自定义Map节点，返回map[string]any
//   - symbolItemName: 符号名称，为空时不输出符号，如果设置，则输出符号，如："line"
func (n *TreeNodeSync[D, V]) ToSliceMapList(fn func(node *TreeNodeSync[D, V]) map[string]any, symbolItemName string) (lines []map[string]any) {
	n.mu.RLock()
	defer n.mu.RUnlock()
	if n.size == 0 || n.children == nil {
		return
	}
	return n._toSliceMapList(n.children, fn, symbolItemName, "")
}

var (
	TreeNodeSyncSymbols = map[string]string{
		"BRANCH":       "├─",
		"EMPTY":        "",
		"INDENT":       "	",
		"FIRST_BRANCH": "┌─",
		"LAST_BRANCH":  "└─",
		"VERTICAL":     "│ ",
	}
)

func (n *TreeNodeSync[D, V]) _toSliceMapList(children []*TreeNodeSync[D, V], fn func(node *TreeNodeSync[D, V]) map[string]any, symbolItemName string, precedingSymbols string) (lines []map[string]any) {
	if children == nil {
		return
	}
	l := len(children)
	lines = make([]map[string]any, 0, l)
	for i, child := range children {
		isCurrentLast := false
		if i == l-1 {
			isCurrentLast = true
		}
		item := fn(child)
		if symbolItemName != "" {
			line := []string{precedingSymbols}
			if isCurrentLast {
				line = append(line, TreeNodeSyncSymbols["LAST_BRANCH"])
			} else {
				line = append(line, TreeNodeSyncSymbols["BRANCH"])
			}
			item[symbolItemName] = strings.Join(line, "")
		}

		lines = append(lines, item)

		if child.size > 0 {
			currentPrecedingSymbols := ""
			if symbolItemName != "" {
				currentPrecedingSymbols = precedingSymbols
				if isCurrentLast {
					currentPrecedingSymbols += TreeNodeSyncSymbols["INDENT"]
				} else {
					currentPrecedingSymbols += TreeNodeSyncSymbols["VERTICAL"]
				}
			}
			lines = append(lines, n._toSliceMapList(child.children, fn, symbolItemName, currentPrecedingSymbols)...)
		}
	}
	return

}

// ChildIDS 获取当前节点下一级子节点的ID切片
func (n *TreeNodeSync[D, V]) ChildIDS() (ids []D) {
	n.mu.RLock()
	defer n.mu.RUnlock()
	if n.size == 0 || n.children == nil {
		return []D{}
	}
	for _, child := range n.children {
		ids = append(ids, child.id)
	}
	return
}

// SubIDS 获取当前节点下全部所有子节点的ID切片
func (n *TreeNodeSync[D, V]) SubIDS() (ids []D) {
	n.mu.RLock()
	defer n.mu.RUnlock()
	if n.size == 0 || n.children == nil {
		return []D{}
	}
	for _, child := range n.children {
		ids = append(ids, child.id)
		if child.size > 0 && n.children != nil {
			ids = append(ids, child.SubIDS()...)
		}
	}
	return
}

// PathIDS 获取RootID节点到当前节点的路径的ID切片
func (n *TreeNodeSync[D, V]) PathIDS() (ids []D) {
	n.mu.RLock()
	defer n.mu.RUnlock()
	list := []D{n.id}
	node := n.Parent()
	for node != nil && node.parent != nil {
		list = append(list, node.id)
		node = node.Parent()
	}
	l := len(list)
	if l == 1 {
		return list
	}
	ids = make([]D, l)
	//倒序IDS
	for i, j := l-1, 0; i >= 0; i-- {
		ids[j] = list[i]
		j++
	}
	return
}

// PathMaps 获取RootID节点到当前节点的路径Maps
func (n *TreeNodeSync[D, V]) PathMaps(fn func(node *TreeNodeSync[D, V]) map[string]any) []map[string]any {
	n.mu.RLock()
	defer n.mu.RUnlock()
	list := []*TreeNodeSync[D, V]{n}
	node := n.parent
	for node != nil && node.parent != nil {
		list = append(list, node)
		node = node.Parent()
	}
	l := len(list)
	listRes := make([]*TreeNodeSync[D, V], l)
	if l > 1 {
		//倒序IDS
		for i, j := l-1, 0; i >= 0; i-- {
			listRes[j] = list[i]
			j++
		}
	} else {
		listRes = list
	}
	maps := make([]map[string]any, 0, len(list))
	for _, v := range listRes {
		maps = append(maps, fn(v))
	}
	return maps
}

// String 获取节点树的字符串表述信息
//   - Stringer String() string 接口实现
func (n *TreeNodeSync[D, V]) String() string {
	n.mu.RLock()
	defer n.mu.RUnlock()
	var b strings.Builder
	b.WriteString(fmt.Sprintf("TreeNodeSync:Root Size(%d)\n", n.Size()))
	data := n.ToSliceMapList(func(node *TreeNodeSync[D, V]) map[string]any {
		return map[string]any{
			"ID":    node.id,
			"PID":   node.pid,
			"Value": node.value,
			"Size":  node.size,
		}
	}, "Line")
	for _, v := range data {
		b.WriteString(fmt.Sprintf("%s ID(%v) PID(%v) Value(%v) Size(%d)\n", v["Line"], v["ID"], v["PID"], v["Value"], v["Size"]))
	}
	return b.String()
}

// PrintTree 打印节点树
func (n *TreeNodeSync[D, V]) PrintTree() {
	fmt.Println(n.String())
}
